package com.kobeliu.entity;

public class Demo_47_sword_42 {

    public static void main(String[] args) {

        int[][] nums1 = new int[3][2];
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));


    }

    public static int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len]; //记录到每个位置的最大值
        int max = nums[0];
        dp[0] = nums[0];
        int i = 1;

        while(i<len){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            max = Math.max(dp[i],max);
            i++;
        }
        return max;
    }
}
